One of the most important societal changes of recent times has been the emergence of the Internet and the World Wide Web (e.g., the Web) as a predominant communications medium. The Internet is a general purpose, public computer network which allows millions of computers all over the world, connected to the Internet, to communicate and exchange digital data with other computers also coupled to the Internet. As new technologies emerge, the speed at which one can connect onto the Internet is ever increasing. New Internet enabled applications include realtime, two-way teleconferencing and videoconferencing, streaming audio and video, peer-to-peer file sharing, etc. With the increasing availability of data transfer bandwidth and the proliferation of broadband connections to the Internet, video-on-demand, HDTV, IP telephony, video teleconferencing, and other types of bandwidth intensive applications will become widespread. Virtually all of these new technologies are digitally based, with their constituent information being delivered over digital communications networks.
Ethernet based networks have become the most prevalent communications standard. Ethernet based networking is the most widely-used local area network (LAN) access method, defined by the IEEE as the 802.3 standard. For example, Ethernet has become so widespread that a specification for “LAN connection” or “network card” generally implies an Ethernet based LAN connection or network card without explicitly saying so. Many desktop PCs come with 10/100 Ethernet ports for either home or business/corporate use. For example, Ethernet based components are used not only to create a small home networks, but to connect to the Internet via a DSL or cable modem, which requires it. A 10/100 port means that it supports both 10BaseT at 10 megabits per second (Mbps) and 100BaseT at 100 Mbps.
Ethernet has evolved over time from twisted pair Ethernet (10/100BaseT), which uses economical telephone wiring and standard RJ-45 connectors, to Fiber-optic Ethernet (10BaseF and 100BaseFX), which uses optical fiber as the transmission media. More modern, high performance networks are expected to use a complete fiber-optic network architecture, spanning from individual buildings (or perhaps homes) to the network backbone.
Ethernet transmits variable length frames from 72 to 1518 bytes in length, each containing a header with the addresses of the source and destination stations and a trailer that contains error correction data. The control and correction of errors in an Ethernet based network is primarily implemented through error control coding schemes. Error control coding, as implemented in an Ethernet frame, incorporates a certain amount of redundant information into the frame that allows the receiver (e.g., a gigabit Ethernet router) to detect and/or correct bit errors occurring in transmission.
Generally, error-control coding techniques are used to detect and/or correct errors that occur in the message transmission in a digital communications system. The transmitting side of the error-control coding adds redundant bits or symbols to the original signal sequence and the receiving side uses these bits or symbols to detect and/or correct any errors that occurred during transmission. Ethernet uses a Cyclic Redundancy Check (CRC) method of error control coding.
Recent advances in fiber optic technology and the use of advanced, high speed fiber optic networks has greatly increased the speed and performance of digital transmission methods. A limiting factor in the efficiency of high performance, fiber optic based Ethernet networks is the successful implementation of high speed ECC digital signal processing. For example, newly emerging 10 Gigabit Ethernet is being adopted to handle the most bandwidth intensive applications. 10 Gigabit Ethernet enables a familiar network technology to be used in LAN, MAN and WAN architectures. For improved efficiency, the well known CSMA/CD method for gaining access to the physical medium is not employed. Only full duplex operation is supported. 10 Gigabit Ethernet uses multimode optical fiber up to 300 meters and singlemode fiber up to 40 kilometers.
A problem exists however, where the high speeds of Gigabit Ethernet networks greatly limit the time available for implementing ECC processing. The Ethernet frames are arriving so fast, the processing time for examining and processing the error control coding portions of the arriving frames is significantly limited. This trend is greatly increasing the cost of the ECC processing hardware that is incorporated into the nodes of the Gigabit Ethernet network (e.g., the switches, routers, add-drop multiplexers, etc.).
Prior art FIG. 1 shows a basic diagram of the operation of a typical prior art CRC checksum processing system 100. As depicted in FIG. 1, system 100 includes a data register 101 and a CRC register 102. The data register 101 and CRC register 102 are both coupled to an exclusive-or logic function 103.
System 100 shows the basic characteristic of CRC checksums, being the fact that each bit of the CRC checksum is a function of each of the data bits of data register 101 and the CRC “history” bits of the CRC register 102. The exclusive-or logic function 103 is used to generate the CRC checksum, referred to simply as the CRC, within the CRC register 102. The exclusive-or logic function is typically implemented using a “tree” of multiple exclusive-or gates. As shown by line 110, individual bits of the data register 101 are shifted out to external circuits (e.g., output data). Each of these bits are combined with CRC bits from CRC register 102 via line 111. Line 115 shows a feed back function of the CRC register 102, whereby each bit of the output of the exclusive-or logic function 103 is “exclusive-or'ed” back into the CRC register 102.
Prior art FIG. 2 shows a basic diagram 200 depicting the relationship between the CRC history bits, the data, and the newly computed CRC. As described above, each bit of data 201 and previous CRC 202 are combined using an exclusive-or function, shown here as a plurality of exclusive-or gates 203a–203d, to obtain the new CRC 205. Thus, even though the data register may be much larger than the CRC register, each bit of data influences the final state of the CRC register. Once the contents of the data register 201 is shifted out to the external circuits (e.g., as output data), the contents of the new CRC register 205 is also shifted out and appended to the end of the data.
The problem for such prior art systems is the high speed processing of the CRC checksums. As described above, a problem exists where the high speeds of Multi-Gigabit Ethernet networks greatly limit the time available for implementing ECC processing. Ethernet frames can be many bytes long. Accordingly, prior art high speed CRC processing systems are designed to process multiple bytes of data at a time. Logic functions, such as the exclusive-or function 103, need to be executed for each bit of the multiple bytes of data that are processed per cycle.
The number of logic operations possible per clock cycle is limited. To perform the large number of logic operations required for multiple byte CRC processing units, prior art implementations use large “trees” of logic gates. For example, in multi-gigabit implementations, the number of successive logic operations possible per clock cycle is typically 8 logic operations or less. The time it takes for a signal to cascade through an exclusive-or gate allows only 8 or less of such gates to be linked (e.g., in a tree). Thus, typical prior art implementations seek to perform as many logic operations in parallel as possible. This leads to very large, wasteful circuit designs having a large number of logic gates dedicated to performing CRC logic functions.
An added complication is the fact that the output CRC needs to accurately reflect the number of valid data bytes in the input data word being processed. For example, in the case of a 64 bit input data word where only data in the first 56 bits is valid, the output CRC needs to reflect only the 56 valid bits. Thus, the CRC processing circuit needs to recognize and properly compute the output CRC for the 56 bit sub-portion of the input data word. These complications are very difficult to handle using the prior art “massively parallel” approach. Typical prior art solutions to this problem involve implementing different processing circuits to handle different cases of valid input data (e.g., 56 bits, 48 bits, 40 bits, etc.).
Additional descriptions of error control coding and CRC processing in particular can be found in “Error Control Coding: Fundamentals and Applications” by Shu Lin and Daniel J. Costello, Jr., ISBN 0-13-283796-X, which is incorporated herein.
Thus what is required is a specific solution for implementing ECC processing within high performance digital transmission networks. What is required is a solution that implements an efficient algorithm for computing the CRC checksums that are used with Ethernet frames. The present invention provides a novel solution to the above requirements.